﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace IncrementalSave
{
    public static class ComparisonHelper
    {
        /// <SUMMARY>Computes the Levenshtein Edit Distance between two enumerables.</SUMMARY>
        /// <TYPEPARAM name="T">The type of the items in the enumerables.</TYPEPARAM>
        /// <PARAM name="x">The first enumerable.</PARAM>
        /// <PARAM name="y">The second enumerable.</PARAM>
        /// <RETURNS>The edit distance.</RETURNS>
        public static int[,] EditDistance<T>(string x, string y)
        {
              // for all i and j, d[i,j] will hold the Levenshtein distance between
              // the first i characters of s and the first j characters of t;
              // note that d has (m+1)x(n+1) values
            int m = x.Count();
            int n = y.Count();
            int[,] d = new int[m,n];

              for(int i = 0; i < m; i++)
                d[i, 0] = i; // the distance of any first string to an empty second string
              for(int j = 0; j < n; j++)
                d[0, j] = j; // the distance of any second string to an empty first string

              for(int j = 1; j < n; j++)
              {
                for(int i = 1;i < m; i++)
                {
                  if( x[i] == y[j])
                    d[i, j] = d[i-1, j-1];      // no operation required
                  else
                      d[i, j] = Math.Minimum
                          (
                              d[i - 1, j] + 1, // a deletion
                              d[i, j - 1] + 1, // an insertion
                              d[i - 1, j - 1] + 1 // a substitution
                          );
                }
              }

            return d;
        }
      
    }
}
